#ifndef QUEUE_H
#define QUEUE_H

class Queen
{
public:
	Queen();
	void SetPos();
private:	
	void backtrack(int i);
	void showanswer();

	const static int N = 8;
	int column[N+1];
	int rup[2*N+1];
	int lup[2*N+1];
	int queen[N+1];
	int num;
};

Queen::Queen()
{

}

void Queen::SetPos()
{
	for (int i = 1; i <=N; ++i)
	{
		column[i] = 1;
		queen[i] = 0;
	}

	for (int i = 1; i <= 2*N; ++i)
	{
		rup[i] = lup[i] = 1;
	}

	num = 0;
	backtrack(1);
}

void Queen::backtrack(int i)
{
	if (i > N)
		showanswer();
	else
	{
		for (int j = 1; j <= N; ++j)
		{
			if (column[j] == 1 && 
				rup[i+j] == 1 &&
				lup[i-j+N] == 1)
			{
				queen[i] = j;
				column[j] = rup[i+j] = lup[i-j+N] = 0;
				backtrack(i+1);
				column[j] = rup[i+j] = lup[i-j+N] = 1;
			}
		}
	}
}

void Queen::showanswer()
{
	cout << ++num << '\n';
	for (int i = 1; i <= N; ++i)
	{
		for (int j = 1; j <= N; ++j)
		{
			if (queen[i] == j)
			{
				cout << " Q";
			}
			else
				cout << " *";
		}
		cout << '\n';
	}
	cout << '\n';
}



#endif